#pragma once
#include <iostream>
#include <assert.h>
#include <vector>
#include <time.h>
#include <cmath>
using namespace std;

template<class K, class V>
struct AVLTreeNode
{
	pair<K, V> _kv;//第一个数据存储key，第二个数据存储value
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf; // balance factor，平衡因子，值为右子树与左子树高度差，右边插入就加一，左边插入减一

	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)  //新节点左右都为空，平衡因子为0
	{}
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;

public:
	 //默认成员函数
	AVLTree() = default; //构造

	AVLTree(const AVLTree<K, V>& t) //拷贝构造
	{
		_root = Copy(t._root);
	}

	AVLTree<K, V>& operator=(AVLTree<K, V> t) //赋值构造
	{
		swap(_root, t._root);
		return *this;
	}

	~AVLTree() //析构
	{
		Destroy(_root);
		_root = nullptr;
	}

	bool Insert(const pair<K, V>& kv)  //和之前的二叉平衡树插入类似
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		//第一步先找到cur应该插入的位置
		Node* parent = nullptr, * cur = _root;
		while (cur)
		{
			parent = cur; //保留其父节点
			if (cur->_kv.first < kv.first)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				cur = cur->_left;
			}
			else return false; //元素重复，插入失败
			
		}

		//第二步插入新节点
		cur = new Node(kv); //新插入节点
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		//第三步更新平衡因子
		while (parent)
		{
			if (cur == parent->_left) //在左侧插入节点，平衡因子减小
				parent->_bf--;
			else //右侧插入节点，平衡因子增大
				parent->_bf++;

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				// 继续往上更新
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2) //和书上相反，因为书上是把左侧插入节点平衡因子增大，这里左侧插入减小
			{
				// 不平衡了，旋转处理，cur为插入节点的父节点，paernt为cur的父节点
				if (parent->_bf == 2 && cur->_bf == 1) //RR型，在子树根节点右子树的右子树插入节点
				{ //逆时针左旋转
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)//LL型，在子树根节点左子树上的左子树插入节点，
				{ //顺时针右旋转
					RotateR(parent);
				}
				else  if (parent->_bf == 2 && cur->_bf == -1) //RL型，在子树根节点右子树上的左子树插入节点
				{//先顺时针右旋变成RR型，再逆时针左旋，最后就是原子树根节点右子树上左子树作为子树根节点。
					RotateRL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1) //LR型，在子树根节点左子树上的右子树插入节点
				{ //先逆时针左旋变成LL型，再顺时针右旋，最后就是原子树根节点左子树上的右子树作为子树根节点。
					RotateLR(parent);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}

		return true;
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key){
				cur = cur->_right;
			}
			else if (cur->_kv.first > key){
				cur = cur->_left;
			}
			else{
				return cur;
			}
		}
		return nullptr;
	}

	Node* LeftMost()
	{
		if (_root == nullptr) return nullptr;
		Node* cur = _root;
		while (cur->_left) cur = cur->_left;
		return cur;
	}

	Node* RightMost()
	{
		if (_root == nullptr) return nullptr;
		Node* cur = _root;
		while (cur->_right) cur = cur->_right;
		return cur;
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	bool IsBalance()
	{
		return _IsBalance(_root);
	}

	int Height()
	{
		return _Height(_root);
	}

	int Size()
	{
		return _Size(_root);
	}

private:  
	int _Size(Node* root)
	{
		return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
	}


	bool _IsBalance(Node* root) 
	{
		if (root == nullptr) return true;
		int leftHeight = _Height(root->_left), rightHeight = _Height(root->_right);
		int diff = rightHeight - leftHeight;
		if (abs(diff) >= 2)
		{
			cout << root->_kv.first << "高度差异常" << endl;
			return false;
		}
		if (diff != root->_bf)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}
		
		return _IsBalance(root->_left) && _IsBalance(root->_right);
	}


	size_t _Height(Node* root)
	{
		if (root == nullptr) return 0;
		size_t leftHeight = _Height(root->_left);
		size_t rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr) return;

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}


	void RotateL(Node* parent) //逆时针左单旋，parent为子树根节点，subR为根右子树，subRL为根右子树的左子树
	{ //subRL变成parene的右边，parent变成subR的左边，subR变成这颗子树的根
		Node* subR = parent->_right, *subRL = subR->_left;
		Node* parentParent = parent->_parent;

		//改变parentt的右子树
		parent->_right = subRL;
		if(subRL != nullptr) //避免为空
			subRL->_parent = parent;

		//改变parent的父节点
		subR->_left = parent;
		parent->_parent = subR;

		//改变子树根节点，调整subR为子树根节点
		if (parentParent == nullptr) { //第一种情况：parent为根节点
			_root = subR;
			subR->_parent = nullptr;
		}
		else{ //第二种情况，parent不是根节点
			if (parentParent->_left == parent) parentParent->_left = subR;
			else parentParent->_right = subR;
			subR->_parent = parentParent;//记得更新子树根节点的父节点
		}
		parent->_bf = subR->_bf = 0;//更新平衡因子
	}

	void RotateR(Node* parent) //顺时针右单旋，arent为根，subL为根左子树，subLR为根左子树的右子树
	{ //subLR变成parene的左边，parent变成subL的右边，subL变成这颗子树的根
		Node* subL = parent->_left, *subLR = subL->_right;
		Node* parentParent = parent->_parent;
		
		//改变parent的左子树
		parent->_left = subLR;
		if (subLR != nullptr) //避免为空
			subLR->_parent = parent;

		//改变parent的父节点
		subL->_right = parent;
		parent->_parent = subL;

		//改变子树根节点，调整subL为子树根节点
		if (parentParent == nullptr){//第一种情况：parent为根节点
			_root = subL;
			subL->_parent = nullptr;
		}
		else{//第二种情况：parent不为根节点
			if (parentParent->_left == parent) parentParent->_left = subL;
			else parentParent->_right = subL;
			subL->_parent = parentParent; //记得更新子树根节点的父节点
		}
		parent->_bf = subL->_bf = 0; //更新平衡因子
	}

	void RotateRL(Node* parent) //先以根节点的右子树进行右旋，再对根节点进行左旋
	{
		Node* subR = parent->_right, *subRL = subR->_left;
		int bf = subRL->_bf; //g

		RotateR(parent->_right);
		RotateL(parent);

		//更新平衡因子
		if (bf == 0) { //其本身就是新增节点, h = 0
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == -1) { //在subRL上的右子树插入节点
			subR->_bf = 1;
			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1) { //在subRL的左子树上插入节点
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = -1;
		}
		else assert(false);
	}

	void RotateLR(Node* parent) //先以根节点的左子树进行右旋，再对根节点进行左旋
	{
		Node* subL = parent->_left, *subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);

		if (bf == 0) { //其本身就是新增节点，h = 0
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1) { //在subL的右子树插入节点
			subL->_bf = -1;
			subLR->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == -1){ //在subL的左子树插入节点
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 1;
		}
		else assert(false);
	}

	void Destroy(Node* root)
	{
		if (root == nullptr)return;

		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}

	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* newRoot = new Node(root->_key, root->_value);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);

		return newRoot;
	}

private:
	Node* _root = nullptr;
};



void TestAVLTree1()
{
	AVLTree<int, int> t;
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.Insert({ e, e });
		//cout << e << "->" << t.IsBalance() << endl;
	}
	t.InOrder();
	cout << endl;

	printf("最左边节点为：%d，最右边节点为：%d\n", t.LeftMost()->_kv.first, t.RightMost()->_kv.first);
	if (t.IsBalance()) printf("AVL树建立成功\n");
	else printf("AVL树建立失败\n");

}

void TestAVLTree2()
{
	const int N = 1e6;
	vector<int>v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++) v.push_back(rand() + i);
	size_t begin2 = clock();
	AVLTree<int, int>t;
	for (auto e : v) {
		t.Insert(make_pair(e, e));
	}
	size_t end2 = clock();

	cout << "Insert：" << end2 - begin2 << endl;
	cout << t.IsBalance() << endl;

	cout << "Height：" << t.Height() << endl;
	cout << "Size：" << t.Size() << endl;


	size_t begin1 = clock();
	for (auto e : v)
	{
		t.Find(e);
	}

	 //随机值
	for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}
	size_t end1 = clock();

	cout << "Find：" << end1 - begin1 << endl;
	cout << t.IsBalance() << endl;

}